package org.hegang.algorithm.heapsort;

import org.hegang.algorithm.common.ArraysUtils;
import org.hegang.algorithm.common.RandomNumber;

import java.util.Arrays;

public class HeapSort {
    /**
     * 维护堆的性质(大顶堆)
     *
     * @param arrays 数组
     * @param n      数组长度
     * @param i      待维护节点的下标
     */
    private static void heapify(int[] arrays, int n, int i) {
        // 父节点
        int largest = i;
        // 二叉树左右孩子节点
        int lSon = largest * 2 + 1;
        int rSon = largest * 2 + 2;
        if (lSon < n && arrays[largest] < arrays[lSon]) {
            largest = lSon;
        }
        if (rSon < n && arrays[largest] < arrays[rSon]) {
            largest = rSon;
        }
        if (largest != i) {
            ArraysUtils.swap(arrays, largest, i);
            // 继续向下递归维护堆的性质
            heapify(arrays, n, largest);
        }
    }

    /**
     * 堆排序入口
     *
     * @param arrays
     * @param n
     */
    public static void heapSort(int[] arrays, int n) {
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arrays, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            ArraysUtils.swap(arrays, i, 0);
            heapify(arrays, i, 0);
        }
    }

    public static void main(String[] args) {
        RandomNumber randomNumber = new RandomNumber();
        int[] insertionSort = randomNumber.generateRandomNumberByRandom(0, 100, 30);
        System.out.println(Arrays.toString(insertionSort));
        heapSort(insertionSort, insertionSort.length);
        System.out.println(Arrays.toString(insertionSort));
    }
}
